package com.example.tencentTrain;

/**
 * 你和你的朋友，两个人一起玩 Nim 游戏：
 *  桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉 1 - 3 块石头。
 *  拿掉最后一块石头的人就是获胜者。
 *
 *  假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
 *
 *  示例 1：
 * 输入：n = 4
 * 输出：false
 * 解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
 *      因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
 *
 *  示例 2：
 * 输入：n = 1
 * 输出：true
 *
 *  示例 3：
 * 输入：n = 2
 * 输出：true
 */
public class Leetcode292_CanWinNim {
    public static void main(String[] args) {
        System.out.println(new Solution().canWinNim(6));
    }

    static class Solution {
        private boolean canWinNim4(int n) {
            return n % 4 != 0;
        }
        /**
         * 动态规划空间优化
         * @param n
         * @return
         */
        private boolean canWinNim3(int n) {
            if (n <= 3) return true;
            boolean tmp1 = true;
            boolean tmp2 = true;
            boolean tmp3 = true;
            boolean res = false;
            for (int i = 3; i < n; i++) {
                res = !tmp1 || !tmp2 || ! tmp3;
                boolean tmp = tmp3;
                boolean tmpp = tmp2;
                tmp3 = res;
                tmp2 = tmp;
                tmp1 = tmpp;
            }
            return res;
        }

        /**
         * 备忘录方式动态规划
         * @param n
         * @return
         */
        private boolean canWinNim2(int n) {
            if (n <= 3) return true;
            boolean[] dp = new boolean[n];
            dp[0] = true;
            dp[1] = true;
            dp[2] = true;
            for (int i = 3; i < n; i++) {
                dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
            }
            return dp[n - 1];
        }

        /**
         * 递归方式动态规划
         * @param n
         * @return
         */
        private boolean canWinNim1(int n) {
            if (n <= 3) return true;
            return !canWinNim1(n - 1) || !canWinNim1(n - 2) || !canWinNim1(n - 3);
        }

        public boolean canWinNim(int n) {
            return canWinNim4(n);
        }
    }
}
